package 力扣.公用数据结构;

import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode() {
    }

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    //将字符串数组看做是是二叉树的顺序存储，null为空节点
    public static TreeNode creat(String s) {
        s = s.substring(1, s.length() - 1);
        if (s.length() == 0)
            return null;
        if (!s.contains(",")) {
            return new TreeNode(Integer.parseInt(s));
        } else {
            String[] splits = s.split(",");
            TreeNode[] list = new TreeNode[splits.length];
            for (int i = 0; i < splits.length; i++) {
                if (Objects.equals(splits[i], "null"))
                    list[i] = null;
                else
                    list[i] = new TreeNode(Integer.parseInt(splits[i]));
            }
            //下标从0开始的左孩子为2i+1,右孩子为2i+2
            for (int i = 0; i <= (splits.length - 2) / 2; i++) {
                if (list[i] != null) {
                    list[i].left = list[i * 2 + 1];
                    if (i * 2 + 2 < list.length)
                        list[i].right = list[i * 2 + 2];
                }
            }
            return list[0];
        }

    }

    public static String treeNodeToString(TreeNode root) {
        if (root == null) {
            return "[]";
        }

        String output = "";
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();

            if (node == null) {
                output += "null, ";
                continue;
            }

            output += String.valueOf(node.val) + ", ";
            nodeQueue.add(node.left);
            nodeQueue.add(node.right);
        }
        return "[" + output.substring(0, output.length() - 2) + "]";
    }

    public static TreeNode stringToTreeNode(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return null;
        }

        String[] parts = input.split(",");
        String item = parts[0];
        TreeNode root = new TreeNode(Integer.parseInt(item));
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.add(root);

        int index = 1;
        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int leftNumber = Integer.parseInt(item);
                node.left = new TreeNode(leftNumber);
                nodeQueue.add(node.left);
            }

            if (index == parts.length) {
                break;
            }

            item = parts[index++];
            item = item.trim();
            if (!item.equals("null")) {
                int rightNumber = Integer.parseInt(item);
                node.right = new TreeNode(rightNumber);
                nodeQueue.add(node.right);
            }
        }
        return root;
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }

    public static void main(String[] args) {
        TreeNode node = stringToTreeNode("[3,9,20,null,null,15,7]");
        System.out.println(node);
    }
}
